
\documentclass[a4paper,10pt]{article}
\usepackage{color}
% \usepackage{fancyhdr}
\usepackage[utf8]{inputenc}

\usepackage{enumerate}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{ulem}
% \usepackage{ifsym}
\usepackage{graphicx}
%\usepackage[margin=3cm]{geometry}

%\renewcommand{\headheight}{16pt}

%\newcommand{\HRule}{\rule{\linewidth}{0.1mm}}

\begin{document}

%\begin{titlepage}
\begin{center}
	\textsc{\Large Distributed Database Systems (WS 11/12) }\\[0.3cm]
	\textsc{\large Assignment 9}\\[1cm]
        Adam Grycner\\
        Szymon Matejczyk\\
        Guo Xinyi\\
        Yu Chenying\\[1cm]
        \today\\[1cm]
        \rule{\linewidth}{0.1mm}\\
 	%\HRule\\
%	\HRule\\[2cm]
	
\end{center}
\section{Exercise 9.1: Discussion}
\begin{enumerate}
  \item Disadvantages of centralized P2P:
      \begin{enumerate}[a.]
      \item Single point of failure for whole network.
      \item Central server can easily become a bottleneck, thus it's not very scalable.
      \end{enumerate}
  \item
    TTL flooding is needed, because flooding messages across whole network would quickly choke the network making it impossible to send anything. TTL makes messages circle only locally and prevents spamming.
  \item Low-bandwidth nodes in pure P2P and hybrid sytems \\
    In pure P2P networks low-bandwidth nodes are unable to transfer data, that is send between other nodes, and they are likely to become bottlenecks. In hybrid systems only strong peers are used for data transmissions and the low-bandwidth ones are connected to the strong ones, which prevents network overload.
\end{enumerate}
\section{Exercise 9.2: Routing Indexes}
First, both P1 and P4 add a new entry for the new neighbor to their routing indexes:\\
Peer1 (row P4 added): \quad\quad\quad\quad\quad\quad\quad\quad\quad Peer4 (row P1 added):\\
\begin{tabular}{c|lllll}
   &\#   &DB &N  &T &L \\
	\hline
P1 &300 &30 &80 &0 &10 \\
P2 &100 &20 &0 &10 &30 \\
P3 &1000 &0 &300 &0 &50 \\
P4 &200 &100 &0 &100 &150
\end{tabular}
\quad\quad
\begin{tabular}{c|lllll}
   &\#   &DB &N  &T &L \\
	\hline
P4 &100 &60 &0 &60 &75 \\
P5 &50 &25 &0 &15 &50 \\
P6 &50 &15 &0 &25 &25 \\
P1 &1400 &50 &380 &10 &90 \\
\end{tabular}
\\
\\Afterwards, the old neighbors of P1 and P4 are updated:\\
Peer2...\\
Peer3...\\
Peer5 (row P4 updated):\quad\quad\quad\quad\quad\quad\quad\quad\quad Peer6 (row P4 updated):\\
\begin{tabular}{c|lllll}
   &\#   &DB &N  &T &L \\
	\hline
P5 &50 &25 &0 &15 &50 \\
P4 &1550 &125 &380 &95 &190
\end{tabular}
\quad\quad
\begin{tabular}{c|lllll}
   &\#   &DB &N  &T &L \\
	\hline
P6 &50 &15 &0 &25 &25 \\
P4 &1550 &135 &380 &85 &215 \\
\end{tabular}

\section{Exercise 9.3: Chord}
a)
\scriptsize
\begin{tabular}{|c|c|c|c|c|c|c|c|}
\hline
p6+1 & p9 \\
\hline
p6+2 & p9 \\
\hline
p6+4 & p11 \\
\hline
p6+8 & p16 \\
\hline
p6+16 & p29 \\
\hline
p6+32 & p42 \\
\hline
\end{tabular}\\
\normalsize
\\
b) p6 uses finger 8 to forward the query to p16. p6 uses finger 1 to forward the query to p21.\\
c) Key45 to p55, key60 to p1.\\
d) [2,6]
\end{document}
